package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/10 14:40
 */
public class C198 {

    // ~打家劫舍~, 暴力解
    public static int rob(int[] nums) {
        return process(nums, 0);
    }

    public static int process(int[] nums, int i) {
        if (i >= nums.length)
            return 0;
        int p1 = nums[i] + process(nums, i + 2);
        int p2 = process(nums, i + 1);
        return Math.max(p1, p2);
    }

    // 记忆化搜索.
    public static int rob2(int[] nums) {
        int[] dp = new int[nums.length + 1];
        Arrays.fill(dp, -1);
        return process2(nums, 0, dp);
    }

    public static int process2(int[] nums, int i, int[] dp) {
        if (i >= nums.length)
            return 0;
        if (dp[i] != -1)
            return dp[i];
        int p1 = nums[i] + process2(nums, i + 2, dp);
        int p2 = process2(nums, i + 1, dp);
        return dp[i] = Math.max(p1, p2);
    }

    // 动态规划.
    public static int dp(int[] nums) {
        int N;
        int[] dp = new int[N = (nums.length + 2)];  // 多占用两个位置, 好让下边少一点判断
        for (int i = N - 3; i >= 0; i--) {
            dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
        }
        return dp[0];
    }

    // 动态规划. 空间压缩
    public static int dp2(int[] nums) {
        int a = 0, b = 0, c = -1;   // c:i, b:i+1, a:i+2
        int N = nums.length;
        for (int i = N - 1; i >= 0; i--) {
            c = Math.max(nums[i] + a, b);
            a = b;
            b = c;
        }
        return c;
    }


    // for test
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(rob(nums));
        System.out.println(rob2(nums));
        System.out.println(dp(nums));
        System.out.println(dp2(nums));
    }

}
